package madixin.t820;

import java.util.HashMap;
import java.util.Map;

class Solution {
    //字符串倒过来建立Trie，统计叶子节点长度
    public int minimumLengthEncoding(String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(reverseString(word));//reverse
        }
        return trie.getLength();
    }

    public String reverseString(String word) {
        StringBuilder res = new StringBuilder(word);
        return res.reverse().toString();
    }

    class Trie {
        private Map<Node, Integer> nodes = new HashMap<Node, Integer>();

        private class Node {
            Node[] childs = new Node[26];
            int childCount = 0;
        }

        private Node root = new Node();

        public Trie() {
        }


        public void insert(String word) {
            insert(word, word, root);
        }

        private void insert(String word, String originWord, Node node) {
            if (node == null) return;
            if (word.length() == 0) {
                nodes.put(node, originWord.length());
                return;
            }
            int index = indexForChar(word.charAt(0));
            if (node.childs[index] == null) {
                node.childs[index] = new Node();
                node.childCount++;
            }
            insert(word.substring(1), originWord, node.childs[index]);
        }

        private int indexForChar(char c) {
            return c - 'a';
        }

        public int getLength() {
            int count = 0;
            for (Node node : nodes.keySet()) {
                if (node.childCount == 0) {
                    count = count + nodes.get(node) + 1;
                }
            }
            return count;
        }
    }
}